문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 튜링 머신 (문단 편집) == 처치-튜링 명제 == Church-Turing thesis. [[알고리즘]]으로 할 수 있는 모든 일이 튜링 기계로 실행될 수 있다는 것이다. 현재까지 알려진 모든 알고리즘들은 튜링 기계로 실행될 수 있다고 추측된다. 그러나 알고리즘의 정의가 명확하지 않으므로 이 명제가 증명되기는 어렵다. [[양자컴퓨터]] 또한 이것을 벗어나지 않는다. 지금까지 알려진 모든 양자컴퓨터는 튜링 기계에 의해 시뮬레이션될 수 있고 역시나 처치-튜링 명제가 성립한다. 대부분의 학자들은 처치-튜링 명제가 참일 것이라고 여기고 있다. 다시 말하자면 위에서 말한 튜링 머신의 한계들은 어떤 방법으로도 해결 불가능할 것이라고 생각되고 있다. 처치-튜링 명제는 사람의 뇌 또한 하나의 컴퓨터에 지나지 않을 수 있음을 암시하고 있다. 그런데 오히려 [[로저 펜로즈]] 등은 인간의 뇌가 컴퓨터와 다른 능력을 지녔으며 그렇기 때문에 처치-튜링 명제가 완전하지 않다고 여긴다. 펜로즈는 [[불완전성 정리]]에 의해 튜링 기계, 다시 말해 모든 기계적 컴퓨터에는 한계가 존재하는데 사람의 뇌는 그렇지 않다는 것이다. 그렇기 때문에 알려지지 않은 어떤 새로운 [[양자역학]]의 개선에 의해 튜링 기계보다 뛰어난 능력을 가질 수 있다는 것이다. 그러나 철학적으로 문제가 많은 주장이기에 주류 학계에서는 진지하게 받아들여지지 않는다. 한국에는 잘 알려지지 않았지만 더 강한 버전으로 Church–Turing–Deutsch principle이란 것이 존재한다. 알고리즘을 넘어서 아예 모든 물리적 과정이 튜링 기계로 시뮬레이션될 수 있다는 것이다. 다만 이 때는 시뮬레이션의 정의도 명확치 않을뿐더러 처치-튜링 명제와 마찬가지로 증명되기는 어려운 성질의 것이다. [[1936년]] [[수리논리학]]자인 알론조 처치가 먼저 제안했기 때문에 처치의 명제를 따로 구분하여 부르기도 한다. 처치의 명제는 결정가능한 모든 계산가능한 함수가 재귀적이라는 것이다. 같은 해인 1936년에 [[앨런 튜링]]이 튜링 머신을 통해 별개의 방향으로 이를 이상화시켜 나타난 개념이 처치-튜링 명제이다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기